Least operators to express number [Math]

Time: O(LogN/LogX); Space: O(LogN); hard

Given a single positive integer x, we will write an expression of the form x (op1) x (op2) x (op3) x … where each operator op1, op2, etc. is either addition, subtraction, multiplication, or division (+, -, , or /). For example, with x = 3, we might write 3 3 / 3 + 3 - 3 which is a value of 3.

When writing such an expression, we adhere to the following conventions:

• The division operator (/) returns rational numbers.

• There are no parentheses placed anywhere. We use the usual order of operations: multiplication and division happens before addition and subtraction. It’s not allowed to use the unary negation operator (-). For example, “x - x” is a valid expression as it only uses subtraction, but “-x + x” is not because it uses negation. We would like to write an expression with the least number of operators such that the expression equals the given target.

Return the least number of operators used.

Example 1:

Input: x = 3, target = 19

Output: 5

Explanation:

• 3 * 3 + 3 * 3 + 3 / 3. The expression contains 5 operations.

Example 2:

Input: x = 5, target = 501

Output: 8

Explanation:

• 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5. The expression contains 8 operations.

Example 3:

Input: x = 100, target = 100000000

Output: 3

Explanation:

• 100 * 100 * 100 * 100. The expression contains 3 operations.

Constraints:

• 2 <= x <= 100

• 1 <= target <= 2 * 10^8

1. Dynamic Programming [O(log_x(target)), O(log(target))]

from functools import lru_cache

class Solution1(object):
    """
    Time: O(log_x(target)). We can prove that we only visit up to two states for each base-x digit of target
    Space: O(log(target))
    """
    def leastOpsExpressTarget(self, x, target):
        cost = list(range(40))
        cost[0] = 2

        @lru_cache(None)
        def dp(i, targ):
            if targ == 0: return 0
            if targ == 1: return cost[i]
            if i >= 39: return float('inf')

            t, r = divmod(targ, x)
            return min(r * cost[i] + dp(i+1, t),
                       (x-r) * cost[i] + dp(i+1, t+1))

        return dp(0, target) - 1

s = Solution1()

x = 3
target = 19
assert s.leastOpsExpressTarget(x, target) == 5

x = 5
target = 501
assert s.leastOpsExpressTarget(x, target) == 8

x = 100
target = 100000000
assert s.leastOpsExpressTarget(x, target) == 3

2. Dynamic Programming [O(1), O(1)]

class Solution2(object):
    """
    Time: O(LogN/LogX)=O(1)
    Space: O(LogN)=O(1)
    """
    def leastOpsExpressTarget(self, x, target):
        """
        :type x: int
        :type target: int
        :rtype: int
        """
        pos, neg, k = 0, 0, 0

        while target:
            target, r = divmod(target, x)
            if k:
                pos, neg = min(r*k + pos, (r+1)*k + neg), \
                           min((x-r)*k + pos, (x-r-1)*k + neg)
            else:
                pos, neg = r*2, (x-r)*2
            k += 1

        return min(pos, k+neg) - 1

s = Solution2()

x = 3
target = 19
assert s.leastOpsExpressTarget(x, target) == 5

x = 5
target = 501
assert s.leastOpsExpressTarget(x, target) == 8

x = 100
target = 100000000
assert s.leastOpsExpressTarget(x, target) == 3

See also:

https://leetcode.com/problems/least-operators-to-express-number